package cn.lbd.arithmetic.leetcode.editor.cn;
//给定一个可包含重复数字的序列，返回所有不重复的全排列。
//
// 示例: 
//
// 输入: [1,1,2]
//输出:
//[
//  [1,1,2],
//  [1,2,1],
//  [2,1,1]
//] 
// Related Topics 回溯算法 
// 👍 419 👎 0


import java.util.*;
import java.util.stream.Collectors;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution47 {

    /*private static List<List<Integer>> records = new ArrayList<>();
    private static int count;

    public static List<List<Integer>> permuteUnique(int[] nums) {
        int n = nums.length;
        dfs(nums, 0, n);
        List<List<Integer>> collect = records.parallelStream()
                .distinct()
                .collect(Collectors.toList());
        return collect;
    }

    *//***
     * 只交换n-1次，及最后一个元素没有交换，要记得输出最后一个元素
     * @param nums
     * @param n
     *//*
    public static void disp(int[] nums, int n) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < (n - 1); i++) {
            list.add(nums[i]);
        }
        list.add(nums[n - 1]);
        list.parallelStream()
                .sorted(Integer::compareTo);
        records.add(list);
        ++count;
    }

    *//**
     * 解空间树是排列树
     *
     * @param nums 数组
     // @param i    叶子层级，从0开始，i>=n
     // @param n    数组元素个数
     *//*
    public static void dfs(int[] nums, int i, int n) {
        if (i >= n) {
            disp(nums, n);
        } else {
            for (int j = i; j < n; j++) {
                swap(nums,i,j);
                dfs(nums, i + 1, n);
                swap(nums,i,j);
            }
        }
    }

    public static void swap(int[] nums,int x, int y) {
        int temp = nums[x];
        nums[x] = nums[y];
        nums[y] = temp;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,2,3};
        List<List<Integer>> lists = permuteUnique(nums);
        System.out.println(lists.toString());
        System.out.println(count);
    }*/
    public List<List<Integer>> permuteUnique(int[] nums) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        // 排序（升序或者降序都可以），排序是剪枝的前提
        Arrays.sort(nums);

        boolean[] used = new boolean[len];
        // 使用 Deque 是 Java 官方 Stack 类的建议
        Deque<Integer> path = new ArrayDeque<>(len);
        dfs(nums, len, 0, used, path, res);
        return res;
    }

    private void dfs(int[] nums, int len, int depth, boolean[] used, Deque<Integer> path, List<List<Integer>> res) {
        if (depth == len) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < len; ++i) {
            if (used[i]) {
                continue;
            }

            // 剪枝条件：i > 0 是为了保证 nums[i - 1] 有意义
            // 写 !used[i - 1] 是因为 nums[i - 1] 在深度优先遍历的过程中刚刚被撤销选择
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }

            path.addLast(nums[i]);
            used[i] = true;

            dfs(nums, len, depth + 1, used, path, res);
            // 回溯部分的代码，和 dfs 之前的代码是对称的
            used[i] = false;
            path.removeLast();
        }
    }

}
//leetcode submit region end(Prohibit modification and deletion)
